Relational databases store information in indexed tables. A user retrieves information from the tables by entering input that is converted to queries by a database application. The database application submits the queries to a database server. In response to a query, the database server accesses the tables specified in the query to determine which information within the tables satisfies the queries. The information that satisfies the queries is then retrieved by the database server and transmitted to the database application and ultimately to the user.
For any given database application, the queries must conform to the rules of a particular query language. Most query languages provide users with a variety of ways to specify information to be retrieved. For example, in the Structured Query Language (SQL), the following query requests the retrieval of the information contained in all rows of a table "t1": EQU SELECT * FROM t1
The user may constrain the query to retrieve a smaller amount of information by adding a WHERE clause, as in the following query: EQU SELECT * FROM t1 EQU WHERE c1=2 AND c2&gt;5 AND c3=8
The WHERE clause imposes a constraint that each row of table t1 must meet to satisfy the query. In this case, the WHERE clause has three predicates, c1=2, c2 &gt;5, and c3=8. These predicates mean that all the retrieved rows of table t1 must have a value equal to two in column c1, a value greater than five in column c2, and a value equal to eight in column c3, respectively.
Without special processing, a database server would have to fetch every row of a table and inspect every column named in the WHERE clause to perform the query. However, such an approach impairs the overall database system performance because many disk blocks would have to be read. As a result, many database systems provide indexes to increase the speed of the data retrieval process. A database index is similar to a normal index found at the end of a book, in that both kinds of indexes comprise an ordered list of information accompanied with the location of the information. Values from one or more columns of a table are stored in an index, maintained separately from the actual database table.
Referring to FIG. 1A, it illustrates a portion of a table 100 and a portion of a B-tree 108 associated with table 100. Table 100 has a plurality of rows 105A-105D, and a plurality of columns 102A-102N. Each table in a database system also has an internal column, or pseudocolumn, referred to as rowid. A table's rowid pseudocolumn is not displayed when the table's structure is listed. However, it is retrievable by a query and can be used to uniquely identify a row in the table. Rowid column 103 has rowid entries that correspond to the rows 105A-105D. Column 102N of table 100 stores names.
A B-tree consists of a set of nodes connected in a hierarchical arrangement. A B-tree contains two types of nodes: branch nodes and leaf nodes. Leaf nodes reside at the lowest level of the hierarchy and contain values from the actual column to which the index corresponds. For example, B-tree 108 is an index for column 102N of table 100. Node 134 of B-tree 108 is a leaf node that contains values from column 102N. Along with the values, leaf nodes store the rowid of the rows that contain the values. For example, in addition to the names Issacs, leaf node 134 contains the rowid 4876 that corresponds to the row 105A of table 100 that contains the name Issacs in column 102N.
All the nodes in B-tree 108 that are not leaf nodes are branch nodes. Branch nodes contain data that indicates a interval of values. In the illustrated B-Tree 108, nodes 110, 112, 114, 116, 120, 122, 124, 132 and 136 are branch nodes, and therefore correspond to intervals of values. The interval of values identified in each branch node is such that all nodes that reside below a given branch node correspond to values that fall within the interval of values represented by the branch node. For example, node 114 is a branch node that corresponds to names in the alphabetic interval from Franklin to Miner. Consequently, nodes 120, 122, 124, 132, 134, and 136 which all reside below node 114 in the hierarchy, correspond to values that fall within the interval of Franklin to Miner. Reference numerals 118, 126, 128, 130, 138 and 140 represent connections to other portions of B-Tree 108 that are not shown.
To search for a value within an indexed column, a database system traverses the B-tree associated with the column. The steps for traversing a B-tree are illustrated in FIG. 1B. Referring to FIG. 1B, at step 150 the highest node in the B-tree hierarchy is established as the current node. For the purposes of illustration, it shall be assumed that a search is being performed for the name "Iverson" in column 102N. Therefore, the highest node of the B-Tree that corresponds to column 102N (node 110) shall be established as the current node at step 150. The value for which a search is being performed shall be referred to hereafter as the "target value". In the present example, "Iverson" is the target value.
At step 152, it is determined whether the target value falls within the interval associated with the highest node. In the illustrated example, the target name "Iverson" falls within the interval "Abbey" to "Zachary" associated with the highest node 110. Therefore control passes to step 158. If the target value did not fall within the interval associated with the highest node, then the target value does not reside in the column associated with the B-Tree 108 and control would pass to step 154.
At step 158, the nodes that reside directly below the current node are inspected to determine the next current node. The next current node is the node below the current node that represents the interval in which the target value resides. In the present example, nodes 112, 114 and 116 reside below the current node 110. Node 114 corresponds to the interval "Franklin" to "Miner", in which the target name "Iverson" resides. Therefore, node 114 is established as the new current node.
At step 160, it is determined whether the current node is a leaf node. In the present example, node 114 is not a leaf node so control passes back to step 158.
At step 158, nodes 120, 122, and 124 which reside directly below the current node 114 are inspected. Node 122 is selected as the next current node because the target name "Iverson" resides within the interval "Hamilton" to "Jones" associated with node 122. At step 160 it is determined that the current node 122 is not a leaf node so control passes back to step 158. At step 158, nodes 132, 134, and 136 are inspected, and node 134 is selected as the next current node because the target name "Iverson" falls within the interval of names contained within node 134.
At step 160, it is determined that the current node 134 is a leaf node and control passes to step 162. At step 162, it is determined whether the current leaf node 134 contains the target value. In the present example, the name "Iverson" is contained in leaf node 134, so control passes to step 156. If the current leaf node does not contain the target value, control passes to step 154 where a signal indicating that the value was not found is generated.
At step 156, a signal is generated indicating that the target value was found within the index, and the rowid associated with the value is also returned. In the illustrated example, the rowid associated with the name "Iverson" is 10005.
For any given query, there may be many indexes which may be used to process the query. For example, assume that a database server receives query: EQU SELECT * FROM t1 EQU WHERE c1=2 AND c2&gt;5 AND c3=8
Assume further that the server has an index built on column c1, an index built on column c2, an index built on column c3, an index built on columns c1,c2 and an index built on columns c3,c4. The database server could select any set of zero or more of these indexes to process the query. However, the efficiency of the query processing may vary greatly based on which indexes are selected.
For example, if all values in column c2 are less than 5, then using an index built on c2 to process the query would generate a significant amount of overhead without any reduction in the number of rows that must be inspected. On the other hand, there may be only one row that contains the value 8 in column c3. Consequently, use of the index built on column c3 will greatly reduce the number of rows that need to be inspected.
Just as the benefit achieved by using a set of indexes will vary based on the set of indexes selected, so will the cost of using the indexes. Each index node visited during the use of an index generally corresponds to an I/O operation. Therefore, the cost of using an index may be measured as the number of index nodes visited during the use of the index plus the number of I/O operations required to retrieve the rows associated with the rowids returned by the index. In the worst case scenario, each data segment that must be retrieved from the database is stored on a separate page, requiring one I/O operation per data segment. Assume this worst case scenario, the cost of using an index may be computed by the formula: EQU Cost=rowids+leaves+height
where
"Cost" is the cost of using the index; PA1 "rowids" is the number of rowids that will be returned by the index based on the search criteria; PA1 "leaves" is the number of leaf nodes that will be visited during the use of the index; and PA1 "height" is the height of the tree.
Referring to FIG. 2, it illustrates a tree index 200 built on a column "col" of a table "t" (not shown). Assume that a database server receives the query: EQU Select * from t
Where col&gt;"bb"
And col&lt;"ga".
Assume also that the database server uses index 200 to process the query. Initially, the database server traverses the index 200 based on the lower bound value "bb". During the traversal, the database server retrieves the root node 202 and follows a link to node 204. Node 204 is retrieved, and the database server follows a link from node 204 to arrive at leaf node 206.
Leaf node 206 is retrieved and inspected to determine that index entry 212 satisfies the search criteria. The database server follows a link from leaf node 206 to the subsequent leaf node 208. Leaf node 208 is retrieved and inspected to determine that entries 214, 216 and 218 satisfy the search criteria. The database server then follows a link from leaf node 208 to the subsequent leaf node 210.
Leaf node 210 is retrieved and inspected to determine that entry 220 satisfies the search criteria, but that other entries in the leaf node 210 are beyond the end boundary of the search criteria. Because the end boundary of the only interval in the search criteria has been reached, the traversal of index 200 is completed. The database server then retrieves the rows indicated by the entries 212-220 that satisfied the criteria.
In the above example, "rowids" is equal to five, since five rowids are returned by the index, "leaves" is equal to three, since three leaf nodes 206, 208 and 210 were retrieved during the index traversal, and "height" is equal to two, since two branch nodes 202 and 204 were retrieved before arriving at a leaf node. Consequently, the total cost of using index 200 in the present example is nine (5+3 +2).
The cost of using an index to process a particular query may accurately be calculated as the index is used to process the query. However, it is desirable to know the cost of using an index before using an index in order to determine whether the index should in fact be used. To assist the database server in the selection of indexes to process a query, techniques have been developed for estimating the cost of using an index to process a particular query.
Of the various components that comprise the cost of using an index, the most difficult component to estimate without actually processing a query is the number of rowids that will be returned based on the search criteria. The "leaves" component of the cost may be estimated by dividing the number of rowids that satisfy the search criteria by the average number of rowids entries in a leaf node. The "height" component of the cost is relatively easy to determine.
One approach to estimating how many rowids will be returned by an index in response to a particular query requires the storage and maintenance of statistical data for each index. The statistical data may include, for example, table cardinalities, index cardinalities, frequencies of distinct attribute values, lowest/highest attribute values, etc. The statistical information for an index is examined in light of interval restrictions specified in a query to determine an estimate of the number of rowids that will satisfy the query. Unfortunately, the statistical data must be refreshed with each or nearly each data update. The overhead associated with maintaining accurate statistical data can often outweigh the benefits achieved by using more efficient indexes to process a query.
Another approach to estimating how many entries of an index will satisfy a particular query uses histograms. Specifically, information about data distribution of index keys and table attributes is collected periodically in the form of histograms or maintained dynamically as approximate distribution functions. Unfortunately, intervals specified in a query are often small and fall far below the histogram/function granularity. In addition, data distribution, after Boolean restrictions are applied, cannot be modeled at all by such "restriction-independent" estimators.
Based on the foregoing, it is clearly desirable to provide a mechanism for determining which indexes should be used to most efficiently process a query. It is further desirable to provide a mechanism for estimating the cost of using an index that does not require an excessive amount of overhead. It is further desirable to provide a relatively low-overhead mechanism for estimating the number of rowids that will be returned by an index in response to interval criteria specified in a query.